#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2021-01-04 2:33 下午
# @Author  : yangdy
# @File    : 2020-01-04.509.斐波那契数
# @Software: PyCharmCE
from tools.my_methods import *


class Solution:
    def fib(self, n: int) -> int:
        # if n <= 1:
        #     return n
        # return self.fib(n - 1) + self.fib(n - 2)
        # @lru_cache()
        # def fib(x):
        #     if x <= 1:
        #         return x
        #     return fib(x - 1) + fib(x - 2)
        # return fib(n)
        # data = [0, 1]
        # for i in range(n-1):
        #     data.append(data[-2] + data[-1])
        # return data[n]
        # a, b = 0, 1
        # for i in range(n):
        #     a, b = b, a + b
        # return a
        # mm = [[1, 0], [0, 1]]
        # data, m, p = [0, 1], [[0, 1], [1, 1]], n

        # def multiply_m(m1, m2):
        #     m3 = [[0, 0], [0, 0]]
        #     for i in range(2):
        #         for j in range(2):
        #             for k in range(2):
        #                 m3[i][j] += m1[i][k] * m2[k][j]
        #     return m3

        # def multiply_v(m, v1):
        #     v2 = [0, 0]
        #     for i in range(2):
        #         for j in range(2):
        #             v2[i] += m[i][j] * v1[j]
        #     return v2
        # for i in range(n):
        #     mm = multiply_m(mm, m)
        # data = multiply_v(m, data)
        # return data[0]
        # while p:
        #     if p & 1:
        #         data = multiply_v(m, data)
        #     p >>= 1
        #     if p:
        #         m = multiply_m(m, m)
        # return data[0]
        # import math
        # return int((math.pow((1 + math.sqrt(5)) / 2, n) - math.pow((1 - math.sqrt(5)) / 2, n)) / math.sqrt(5))
        # import math
        # sqrt5 = math.sqrt(5)
        # return int((math.pow((1 + sqrt5) / 2, n) - math.pow((1 - sqrt5) / 2, n)) / sqrt5)
        # return int((((1 + 5**0.5) / 2) ** n - ((1 - 5 ** 0.5) / 2) ** n) / (5**0.5) )
        import math
        def quick_multiply(x, n):
            p, ret = n, 1.0
            while p:
                if p & 1:
                    ret *= x
                p >>= 1
                if p:
                    x *= x
            return ret

        sqrt5 = math.sqrt(5)
        ans = (quick_multiply((1 + sqrt5) / 2, n) - quick_multiply((1 - sqrt5) / 2, n)) / sqrt5
        print(ans, int(ans), round(ans))
        return int(ans)


questions = [
    (10,),
]

work(questions, lambda q: Solution().fib(q[0]))
